In a cellular wireless communication system, an area is divided into cells and cell sectors, each defined by a radiation pattern (on a particular frequency) from a respective base transceiver station (BTS). Each BTS is then typically connected with a base station controller (BSC), which, together with the BTS defines a “base station.” Further, the BSC may then be connected with a switch or gateway that provides connectivity with a transport network such as the public switched telephone network (PSTN) or the Internet. Conveniently with this arrangement, a cell phone or other wireless communication device (generally “mobile station”) that is positioned within the coverage area of a given sector can communicate over an air interface with the BTS and in turn via the BSC and switch or gateway with entities on the transport network.
Unlike landline telephones that exist at known, fixed locations, mobile stations can operate at virtually any location where a wireless carrier provides coverage. Consequently, in order for a mobile station to be able to engage in useful communications (voice or data) in the cellular wireless communication system, the mobile station must first register with the system, so that the system knows where the mobile station is located (e.g., for purposes of directing calls to the mobile station) and so that the system can verify that the mobile station is authorized to be operating in the system.
The manner in which a mobile station registers with a cellular wireless communication system can take various forms, depending on factors such as the configuration of the system and on the communication protocols used. In a system operating according to the well known CDMA2000 protocol, for instance, a mobile station registers by sending over the air to the base station an “access probe,” which carries an identifier of the mobile station and perhaps other pertinent information. The mobile station sends the access probe in a “slotted aloha process” in which it repeatedly sends the access probe at increasingly higher power levels until it receives an acknowledgement message from the base station, or until it otherwise exhausts the process (e.g., the maximum transmission power of the mobile station is reached and no acknowledgment has been received). The mobile station may repeat a slotted aloha sequence a number of times, until concluding that an access failure has occurred. Each access probe travels in a timeslot of an air interface access channel to the base station, and an acknowledgement travels in a timeslot of an air interface paging channel from the base station.
In a given sector, the slotted aloha process proceeds according to operational parameters that are broadcast in a “system parameters message” on the paging channel to mobile stations operating in the sector. Under CDMA2000, for instance, the operational parameters include:                (1) INIT POWER. The power at which the mobile station should transmit its initial access probe in a slotted aloha sequence.        (2) POWER STEP. The extent to which the mobile station should increase transmit power for each successive access probe in the slotted aloha sequence.        (3) NUMBER OF PROBES. The number of access probes per slotted aloha sequence, e.g., after the first access probe.        (4) MAX NUMBER OF REQUEST SEQUENCES. The maximum number of slotted aloha sequences the mobile station should apply when placing a call (i.e., before concluding that the attempt to place the call failed).        (5) MAX NUMBER OF RESPONSE SEQUENCES. The maximum number of slotted aloha sequences the mobile station should apply when receiving a call (i.e., before concluding the that the attempt to receive the call failed).        (6) PROBE PN RAN. A value that is used to reduce access probe collisions when multiple mobile stations might simultaneously send access probes. A mobile station selects an integer number from (i) 0 to (ii) 2 to the power of PROBE PN RAN, by applying a hash function keyed to the mobile station's unique electronic serial number (ESN). When a user presses the “TALK” key on the mobile station to place or receive a call, the mobile station then waits that integer number of chips (each 26.67 milliseconds) before sending its first access probe. Consequently, when users seek to establish calls at the same moment, the PROBE PN RAN value would work to spread apart the times when the mobile stations send their access probes.        
When the base station receives an access probe from a mobile station, the base station then passes the access probe along to the switch (mobile switching center (MSC)) or other entity, which then responsively sends a registration notification message to the mobile station's home location register (HLR). The HLR then updates the mobile station's profile to indicate where the mobile station is operating (e.g., which switch is serving the mobile station) and may further carry out an authentication process, and then sends a registration response, which propagates to the mobile station.
Various trigger events can cause mobile stations to register with the system. In a CDMA2000 system, for instance, a mobile station will generally register (i) whenever it enters a new zone, as indicated by a distinct “reg zone” parameter the mobile station receives in an air interface control channel message from the base station, (ii) on a periodic basis, with a period indicated by a “reg_period” parameter that the mobile station receives in an air interface control channel message from the base station, (iii) when the mobile station places a call, as a prerequisite to call placement, and (iv) when the mobile station responds to a page message indicative of an incoming call.
In some situations, the air interface (e.g., a particular sector defined by a base station) can become overwhelmed with too much use. This can happen, by way of example, if too many mobile station registrations occur at once. In a CDMA2000 system, for instance, if access probes from two or more mobile stations line up (by chance) in the same timeslot of the access channel, an “access probe collision” occurs. The result of such a collision is that none of the probes will succeed, principally because the base station will not receive any of the probes in a comprehensible form due to interference between the probes. Thus, each mobile station would have to re-send its access probe, because it would not receive an acknowledgement from the base station.
In many situations, access probe collisions are not very likely to occur, because sufficient timeslots exist on the access channel. However, in situations where many users are placing calls at once, the number of access probes and access probe collisions can increase exponentially (or at least greatly). For example, after a football game or in an emergency situation, many people within a given sector may use their mobile phones to place calls (e.g., to call 911, to call friends and family, to check voice mail, or for other purposes). Each time a mobile station goes to place a call, as noted above, the mobile station would send an access probe. Consequently, in a situation where many people within a given sector place calls at once, many access probes will be sent at once. In turn, access probe collisions would occur, and so still more (re-try) access probes will be sent. Further, as this is occurring, mobile stations will be periodically registering with the system, according to the “reg_period” directive from the base station, which will still further increase the frequency of access probe collisions.
Unfortunately, as the access channel becomes more and more occupied with access probes, two undesired effects will tend to occur. First, the number of access probe collisions will tend to increase, which means that registrations will take longer to successfully complete. In placing and receiving calls, this longer registration process translates into longer call setup time, which in turn translates into an unacceptable user experience. Second, as mobile stations exhaust the slotted aloha process, the number of ultimate access failures will tend to increase. In placing and receiving calls, these access failures will be perceived as blocked calls, which will also result in unacceptable user experience. Therefore, an improvement is desired.